Aufgabe 3.2.3:

Die Übergangstabelle eines DEA siehe wie folgt aus:

\begin{aligned}& 0 & 1 \\ → p^{∗} & s & p \\ q & p & s \\ r & r & q \\ s & q & r \end{aligned}

Die Graph eines DEA sehe wie folgt aus:

p  sq  r 1  0 00 1 0 11

Als erstes werden die Zeichenketten an den Pfeilen des Graphen als Ausdrücke geschrieben, in dem sie fett geschrieben werden. Diesen Schritt sparen wir uns, da es nichts am Aussehen und der Struktur des Graphen ändert. Statt dessen werden wir gleich dazu übergehen den ersten Zustand des Graphen zu eliminieren. Dieser ist im Grunde frei wählbar. Am Schluss muss der Graph bis auf 2 Zustände reduziert sein, den Start- und den Endzustand. Da diese beiden in diesem Fall p sind, wird der minimierte Automat am Ende nur noch aus einem Zustand, nämlich p bestehen. Als erstes werden wir Zustand q eliminieren. Dazu muss jeder Pfad der über q führt zu einem neuen Pfad gemacht werden, der ohne den Zustand q auskommt.Welche Pfade müssen hier also erzeugt werden:

a) Ein Pfad führt von r über q nach s.

b) Ein Pfad führt von r über q nach p.

c) Ein Pfad führt von s über q nach p.

d) Ein Pfad führt von s über q zurück nach s.

Wir müssen also für jeden der Möglichen Pfade über q (a, b, c, und d) einen Ausdruck formulieren, der die Zeichenreihe beschreibt, welche auf genau diesen Pfaden steht. a) Der Pfad von r über q nach s wird beschriftet mit 11.

Von r aus kommt eine 1 (was zu Zustand q führt), gefolgt von einer 1 (was den Zustand des Automaten dann von q auf s ändert, womit wir den gesuchten Pfad abgedeckt hätten. Dies führt zu folgendem Automaten:

p  sq  r  0 1  0 0 1 0 1 111

Die "‘ersetzten"’ Pfade werden hier noch nicht entfernt, da sonst bei weiteren Schritten leicht Fehler auftreten könnten.

b) Der Pfad von r über q nach p wird beschriftet mit 11. Erklärung analog zu oben. Dies führt zu folgendem Automaten:

p  sq  r  0 1  0 0 1 0 1 111 10

c) Der Pfad von s über q nach p wird beschriftet mit 00

p  sq  r  0 1  0 0 1 0 1 111 10 00

d) Der Pfad von s über q zuück zu s wird beschriftet mit 01.

p  sq  r  0 1  0 0 1 0 1 111 10 00  01

Nun kann man alle ersetzten Pfade weglassen, was zu diesem Automaten führt:

p  s  r  0 1  0  111 10 00  01

Im nächsten Schritt wird Zustand r eliminiert. Dazu wird genau das selbe Schema wie oben angewendet.

a) Ein Pfad führt von s über r zu p.

b) Ein Pfad führt von s über r zurück nach s. a) Der Pfad von s über r zu p wird beschriftet mit 10^{∗}10. Da es aber schon einen

Pfad von s nach p gibt, wird der existierenden Pfad mit einer Vereinigung des alten und des neuen Ausdrucks beschriftet:

p  s  r  0 1  0  111 10 00 + 10^{∗}10 01

b) Der Ausdruck auf dem schon existierenden Pfad von s zu sich selbst, wird nun noch mit dem Ausdruck für den Pfad von s über r zurück zu s (10^{∗}11) vereinigt:

p  s  r  0 1  0  111 10 00 + 10^{∗}1001 + 10^{∗}11

Nun können sowohl der Zustand r als auch alle Pfade zu und von r weggelassen werden. Dies führt zu folgendem Automaten:

p  s 1  0 00 + 10^{∗}1001 + 10^{∗}11

Als letztes muss nun noch der Zustand s eliminiert werden, damit der Automat minimal ist. Dazu muss nur der Pfad beschrieben werden, der von p über s zurück zu q führt. Dieser lautet 0(01 + 10^{∗}11)^{∗}(00 + 10^{∗}10). Dies ist der Pfad von p nach p. Dieser wird vereinigt mit dem schon existierenden Pfad, was zum finalen Automaten führt, an dem mal gleichzeitig den finalen Ausdruck ablesen kann:

p  1 + 0(01 + 10^{∗}11)^{∗}(00 + 10^{∗}10)

Damit lautet der reguläre Ausdruck, der duch Eliminierung von Zuständen erzeugt wurde:

(1 + 0(01 + 10^{∗}11)^{∗}(00 + 10^{∗}10))^{∗}  (1)

Dass vom Ausdruck die kleensche Hülle gebildet werden muss erklärt sich dadurch, dass der Automat auch schon ohne Eingabe akzepiert - beduetet: der Ausdruck der zum akzeptierenden Zustand führt, kann beliebig oft (auch 0 mal) auftreten.